PittsburghV1, France, Analysis, bibRecord, 000493

Verifiable sufficient conditions for l1 recovery of sparse signals

Identifieur interne : 000493 ( France/Analysis ); précédent : 000492; suivant : 000494

Verifiable sufficient conditions for l1 recovery of sparse signals

Auteurs : Anatoli Juditsky [France] ; Fatma Kilinc Karzan [États-Unis] ; Arkadii S. Nemirovski [États-Unis]

Source :

RBID : Hal:hal-00981900

Abstract

In this talk, we will cover some of the recent developments in large-scale optimization motivated by the compressed sensing paradigm. The majority of results in compressed sensing theory rely on the ability to design/use sensing matrices with good recoverability properties, yet there is not much known in terms of how to verify them efficiently. This will be the focus of this talk. We will analyze the usual sparse recovery framework as well as the case when a priori information is given in the form of sign restrictions on the signal. We will propose necessary and sufficient conditions for a sensing matrix to allow for exact l1-recovery of sparse signals and utilize them. These conditions, although difficult to evaluate, lead to sufficient conditions that can be efficiently verified via linear or semidefinite programming. We will analyze the properties of these conditions while making connections to disjoint bilinear programming and introducing a new and efficient bounding schema for such programs. We will finish by presenting limits of performance of these conditions and numerical results.

Url:

https://hal.archives-ouvertes.fr/hal-00981900

Affiliations:

Links toward previous steps (curation, corpus...)

to stream Hal, to step Corpus: 000687
to stream Hal, to step Curation: 000687
to stream Hal, to step Checkpoint: 000353
to stream Main, to step Merge: 007B50
to stream Main, to step Curation: 007675
to stream Main, to step Exploration: 007675
to stream France, to step Extraction: 000493

Links to Exploration step

Hal:hal-00981900

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Verifiable sufficient conditions for l1 recovery of sparse signals</title>
<author><name sortKey="Juditsky, Anatoli" sort="Juditsky, Anatoli" uniqKey="Juditsky A" first="Anatoli" last="Juditsky">Anatoli Juditsky</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-389963" status="OLD">          <orgName>Statistique Apprentissage Machine</orgName>
          <orgName type="acronym">SAM</orgName>
          <date type="start">2011-01-01</date>
          <date type="end">2015-11-30</date>
          <desc>            <address>              <country key="FR"></country>
            </address>
          </desc>
          <listRelation>            <relation active="#struct-24474" type="direct"></relation>
            <relation active="#struct-3886" type="indirect"></relation>
            <relation active="#struct-51016" type="indirect"></relation>
            <relation active="#struct-300339" type="indirect"></relation>
            <relation name="UMR5224" active="#struct-441569" type="indirect"></relation>
            <relation active="#struct-445543" type="indirect"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-24474" type="direct"><org type="laboratory" xml:id="struct-24474" status="VALID">          <idno type="IdRef">184945011</idno>
          <idno type="RNSR">200711891Z</idno>
          <orgName>Laboratoire Jean Kuntzmann</orgName>
          <orgName type="acronym">LJK</orgName>
          <date type="start">2007-01-01</date>
          <desc>            <address>              <addrLine>Bâtiment IMAG, CS 40700, F-38058 Grenoble Cedex 9</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://ljk.imag.fr</ref>
          </desc>
          <listRelation>            <relation active="#struct-3886" type="direct"></relation>
            <relation active="#struct-51016" type="direct"></relation>
            <relation active="#struct-300339" type="direct"></relation>
            <relation name="UMR5224" active="#struct-441569" type="direct"></relation>
            <relation active="#struct-445543" type="direct"></relation>
          </listRelation>
        </org>
</tutelle>
<tutelle active="#struct-3886" type="indirect"><org type="institution" xml:id="struct-3886" status="OLD">          <idno type="IdRef">02640432X</idno>
          <orgName>Université Pierre Mendès France - Grenoble 2</orgName>
          <orgName type="acronym">UPMF</orgName>
          <date type="end">2015-12-31</date>
          <desc>            <address>              <addrLine>BP 47 - 38040 Grenoble Cedex 9</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.upmf-grenoble.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle active="#struct-51016" type="indirect"><org type="institution" xml:id="struct-51016" status="OLD">          <idno type="IdRef">026404796</idno>
          <orgName>Université Joseph Fourier - Grenoble 1</orgName>
          <orgName type="acronym">UJF</orgName>
          <date type="end">2015-12-31</date>
          <desc>            <address>              <addrLine>BP 53 - 38041 Grenoble Cedex 9</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.ujf-grenoble.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle active="#struct-300339" type="indirect"><org type="institution" xml:id="struct-300339" status="VALID">          <orgName>Institut Polytechnique de Grenoble - Grenoble Institute of Technology</orgName>
          <desc>            <address>              <country key="FR"></country>
            </address>
          </desc>
        </org>
</tutelle>
<tutelle name="UMR5224" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID">          <idno type="IdRef">02636817X</idno>
          <idno type="ISNI">0000000122597504</idno>
          <orgName>Centre National de la Recherche Scientifique</orgName>
          <orgName type="acronym">CNRS</orgName>
          <date type="start">1939-10-19</date>
          <desc>            <address>              <country key="FR"></country>
            </address>
            <ref type="url">http://www.cnrs.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle active="#struct-445543" type="indirect"><org type="institution" xml:id="struct-445543" status="VALID"><idno type="IdRef">188399275</idno>
<orgName>Université Grenoble Alpes</orgName>
<orgName type="acronym">UGA</orgName>
<date type="start">2016-01-01</date>
<desc><address><addrLine>CS 40700 - 38058 Grenoble cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-grenoble-alpes.fr</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Grenoble</settlement>
<region type="region" nuts="2">Auvergne-Rhône-Alpes</region>
<region type="old region" nuts="2">Rhône-Alpes</region>
</placeName>
<orgName type="university">Université Joseph Fourier</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Grenoble</orgName>
<placeName><settlement type="city">Grenoble</settlement>
<region type="region" nuts="2">Auvergne-Rhône-Alpes</region>
<region type="old region" nuts="2">Rhône-Alpes</region>
</placeName>
<orgName type="university">Université Grenoble-Alpes</orgName>
</affiliation>
</author>
<author><name sortKey="Kilinc Karzan, Fatma" sort="Kilinc Karzan, Fatma" uniqKey="Kilinc Karzan F" first="Fatma" last="Kilinc Karzan">Fatma Kilinc Karzan</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-94189" status="VALID">          <orgName>School of Industrial and Systems Engineering [Georgia Tech]</orgName>
          <orgName type="acronym">ISyE</orgName>
          <desc>            <address>              <addrLine>H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology 765 Ferst Drive, NW Atlanta, Georgia 30332-0205</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.isye.gatech.edu/</ref>
          </desc>
          <listRelation>            <relation active="#struct-301737" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-301737" type="direct"><org type="institution" xml:id="struct-301737" status="VALID">          <orgName>Georgia Institute of Technology (Georgia Tech)</orgName>
          <desc>            <address>              <addrLine>A. French Building 237 Uncle Heinie Way, Suite 111 Atlanta, GA 30332-0605</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.gatech.edu/</ref>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
</affiliation>
</author>
<author><name sortKey="Nemirovski, Arkadii S" sort="Nemirovski, Arkadii S" uniqKey="Nemirovski A" first="Arkadii S." last="Nemirovski">Arkadii S. Nemirovski</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-94189" status="VALID">          <orgName>School of Industrial and Systems Engineering [Georgia Tech]</orgName>
          <orgName type="acronym">ISyE</orgName>
          <desc>            <address>              <addrLine>H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology 765 Ferst Drive, NW Atlanta, Georgia 30332-0205</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.isye.gatech.edu/</ref>
          </desc>
          <listRelation>            <relation active="#struct-301737" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-301737" type="direct"><org type="institution" xml:id="struct-301737" status="VALID">          <orgName>Georgia Institute of Technology (Georgia Tech)</orgName>
          <desc>            <address>              <addrLine>A. French Building 237 Uncle Heinie Way, Suite 111 Atlanta, GA 30332-0605</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.gatech.edu/</ref>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:hal-00981900</idno>
<idno type="halId">hal-00981900</idno>
<idno type="halUri">https://hal.archives-ouvertes.fr/hal-00981900</idno>
<idno type="url">https://hal.archives-ouvertes.fr/hal-00981900</idno>
<date when="2012-08-19">2012-08-19</date>
<idno type="wicri:Area/Hal/Corpus">000687</idno>
<idno type="wicri:Area/Hal/Curation">000687</idno>
<idno type="wicri:Area/Hal/Checkpoint">000353</idno>
<idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">000353</idno>
<idno type="wicri:Area/Main/Merge">007B50</idno>
<idno type="wicri:Area/Main/Curation">007675</idno>
<idno type="wicri:Area/Main/Exploration">007675</idno>
<idno type="wicri:Area/France/Extraction">000493</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">Verifiable sufficient conditions for l1 recovery of sparse signals</title>
<author><name sortKey="Juditsky, Anatoli" sort="Juditsky, Anatoli" uniqKey="Juditsky A" first="Anatoli" last="Juditsky">Anatoli Juditsky</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-389963" status="OLD">          <orgName>Statistique Apprentissage Machine</orgName>
          <orgName type="acronym">SAM</orgName>
          <date type="start">2011-01-01</date>
          <date type="end">2015-11-30</date>
          <desc>            <address>              <country key="FR"></country>
            </address>
          </desc>
          <listRelation>            <relation active="#struct-24474" type="direct"></relation>
            <relation active="#struct-3886" type="indirect"></relation>
            <relation active="#struct-51016" type="indirect"></relation>
            <relation active="#struct-300339" type="indirect"></relation>
            <relation name="UMR5224" active="#struct-441569" type="indirect"></relation>
            <relation active="#struct-445543" type="indirect"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-24474" type="direct"><org type="laboratory" xml:id="struct-24474" status="VALID">          <idno type="IdRef">184945011</idno>
          <idno type="RNSR">200711891Z</idno>
          <orgName>Laboratoire Jean Kuntzmann</orgName>
          <orgName type="acronym">LJK</orgName>
          <date type="start">2007-01-01</date>
          <desc>            <address>              <addrLine>Bâtiment IMAG, CS 40700, F-38058 Grenoble Cedex 9</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://ljk.imag.fr</ref>
          </desc>
          <listRelation>            <relation active="#struct-3886" type="direct"></relation>
            <relation active="#struct-51016" type="direct"></relation>
            <relation active="#struct-300339" type="direct"></relation>
            <relation name="UMR5224" active="#struct-441569" type="direct"></relation>
            <relation active="#struct-445543" type="direct"></relation>
          </listRelation>
        </org>
</tutelle>
<tutelle active="#struct-3886" type="indirect"><org type="institution" xml:id="struct-3886" status="OLD">          <idno type="IdRef">02640432X</idno>
          <orgName>Université Pierre Mendès France - Grenoble 2</orgName>
          <orgName type="acronym">UPMF</orgName>
          <date type="end">2015-12-31</date>
          <desc>            <address>              <addrLine>BP 47 - 38040 Grenoble Cedex 9</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.upmf-grenoble.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle active="#struct-51016" type="indirect"><org type="institution" xml:id="struct-51016" status="OLD">          <idno type="IdRef">026404796</idno>
          <orgName>Université Joseph Fourier - Grenoble 1</orgName>
          <orgName type="acronym">UJF</orgName>
          <date type="end">2015-12-31</date>
          <desc>            <address>              <addrLine>BP 53 - 38041 Grenoble Cedex 9</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.ujf-grenoble.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle active="#struct-300339" type="indirect"><org type="institution" xml:id="struct-300339" status="VALID">          <orgName>Institut Polytechnique de Grenoble - Grenoble Institute of Technology</orgName>
          <desc>            <address>              <country key="FR"></country>
            </address>
          </desc>
        </org>
</tutelle>
<tutelle name="UMR5224" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID">          <idno type="IdRef">02636817X</idno>
          <idno type="ISNI">0000000122597504</idno>
          <orgName>Centre National de la Recherche Scientifique</orgName>
          <orgName type="acronym">CNRS</orgName>
          <date type="start">1939-10-19</date>
          <desc>            <address>              <country key="FR"></country>
            </address>
            <ref type="url">http://www.cnrs.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle active="#struct-445543" type="indirect"><org type="institution" xml:id="struct-445543" status="VALID"><idno type="IdRef">188399275</idno>
<orgName>Université Grenoble Alpes</orgName>
<orgName type="acronym">UGA</orgName>
<date type="start">2016-01-01</date>
<desc><address><addrLine>CS 40700 - 38058 Grenoble cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-grenoble-alpes.fr</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Grenoble</settlement>
<region type="region" nuts="2">Auvergne-Rhône-Alpes</region>
<region type="old region" nuts="2">Rhône-Alpes</region>
</placeName>
<orgName type="university">Université Joseph Fourier</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Grenoble</orgName>
<placeName><settlement type="city">Grenoble</settlement>
<region type="region" nuts="2">Auvergne-Rhône-Alpes</region>
<region type="old region" nuts="2">Rhône-Alpes</region>
</placeName>
<orgName type="university">Université Grenoble-Alpes</orgName>
</affiliation>
</author>
<author><name sortKey="Kilinc Karzan, Fatma" sort="Kilinc Karzan, Fatma" uniqKey="Kilinc Karzan F" first="Fatma" last="Kilinc Karzan">Fatma Kilinc Karzan</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-94189" status="VALID">          <orgName>School of Industrial and Systems Engineering [Georgia Tech]</orgName>
          <orgName type="acronym">ISyE</orgName>
          <desc>            <address>              <addrLine>H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology 765 Ferst Drive, NW Atlanta, Georgia 30332-0205</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.isye.gatech.edu/</ref>
          </desc>
          <listRelation>            <relation active="#struct-301737" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-301737" type="direct"><org type="institution" xml:id="struct-301737" status="VALID">          <orgName>Georgia Institute of Technology (Georgia Tech)</orgName>
          <desc>            <address>              <addrLine>A. French Building 237 Uncle Heinie Way, Suite 111 Atlanta, GA 30332-0605</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.gatech.edu/</ref>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
</affiliation>
</author>
<author><name sortKey="Nemirovski, Arkadii S" sort="Nemirovski, Arkadii S" uniqKey="Nemirovski A" first="Arkadii S." last="Nemirovski">Arkadii S. Nemirovski</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-94189" status="VALID">          <orgName>School of Industrial and Systems Engineering [Georgia Tech]</orgName>
          <orgName type="acronym">ISyE</orgName>
          <desc>            <address>              <addrLine>H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology 765 Ferst Drive, NW Atlanta, Georgia 30332-0205</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.isye.gatech.edu/</ref>
          </desc>
          <listRelation>            <relation active="#struct-301737" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-301737" type="direct"><org type="institution" xml:id="struct-301737" status="VALID">          <orgName>Georgia Institute of Technology (Georgia Tech)</orgName>
          <desc>            <address>              <addrLine>A. French Building 237 Uncle Heinie Way, Suite 111 Atlanta, GA 30332-0605</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.gatech.edu/</ref>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
</affiliation>
</author>
</analytic>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">In this talk, we will cover some of the recent developments in large-scale optimization motivated by the compressed sensing paradigm. The majority of results in compressed sensing theory rely on the ability to design/use sensing matrices with good recoverability properties, yet there is not much known in terms of how to verify them efficiently. This will be the focus of this talk. We will analyze the usual sparse recovery framework as well as the case when a priori information is given in the form of sign restrictions on the signal. We will propose necessary and sufficient conditions for a sensing matrix to allow for exact l1-recovery of sparse signals and utilize them. These conditions, although difficult to evaluate, lead to sufficient conditions that can be efficiently verified via linear or semidefinite programming. We will analyze the properties of these conditions while making connections to disjoint bilinear programming and introducing a new and efficient bounding schema for such programs. We will finish by presenting limits of performance of these conditions and numerical results.</div>
</front>
</TEI>
<affiliations><list><country><li>France</li>
<li>États-Unis</li>
</country>
<region><li>Auvergne-Rhône-Alpes</li>
<li>Rhône-Alpes</li>
</region>
<settlement><li>Grenoble</li>
</settlement>
<orgName><li>Université Grenoble-Alpes</li>
<li>Université Joseph Fourier</li>
<li>Université de Grenoble</li>
</orgName>
</list>
<tree><country name="France"><region name="Auvergne-Rhône-Alpes"><name sortKey="Juditsky, Anatoli" sort="Juditsky, Anatoli" uniqKey="Juditsky A" first="Anatoli" last="Juditsky">Anatoli Juditsky</name>
</region>
</country>
<country name="États-Unis"><noRegion><name sortKey="Kilinc Karzan, Fatma" sort="Kilinc Karzan, Fatma" uniqKey="Kilinc Karzan F" first="Fatma" last="Kilinc Karzan">Fatma Kilinc Karzan</name>
</noRegion>
<name sortKey="Nemirovski, Arkadii S" sort="Nemirovski, Arkadii S" uniqKey="Nemirovski A" first="Arkadii S." last="Nemirovski">Arkadii S. Nemirovski</name>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Amérique/explor/PittsburghV1/Data/France/Analysis

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000493 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/France/Analysis/biblio.hfd -nk 000493 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Amérique
   |area=    PittsburghV1
   |flux=    France
   |étape=   Analysis
   |type=    RBID
   |clé=     Hal:hal-00981900
   |texte=   Verifiable sufficient conditions for l1 recovery of sparse signals
}}

This area was generated with Dilib version V0.6.38.
Data generation: Fri Jun 18 17:37:45 2021. Site generation: Fri Jun 18 18:15:47 2021

	Serveur d'exploration sur Pittsburgh
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur Pittsburgh

Verifiable sufficient conditions for l1 recovery of sparse signals

Verifiable sufficient conditions for l1 recovery of sparse signals

Source :

Abstract

Links toward previous steps (curation, corpus...)

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri